package jun;

import com.sun.scenario.animation.shared.ClipEnvelope;

import java.io.File;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.*;

/**
 * @author ：冯涛滔
 * @date ：Created in 2020-6-5 10:25
 * @description：
 * @modified By：
 * @version:
 */
public class Jun05 {
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/score-after-flipping-matrix/solution/fan-zhuan-ju-zhen-hou-de-de-fen-by-leetcode/
     * 看看就好
     * create time: 2020-6-5 10:30
     *
     * @return int
     * @params [A]
     */
    public int matrixScore(int[][] A) {

        int R = A.length, C = A[0].length;
        int ans = 0;
        for (int c = 0; c < C; ++c) {
            int col = 0;
            for (int r = 0; r < R; ++r)
                col += A[r][c] ^ A[r][0];
            ans += Math.max(col, R - col) * (1 << (C - 1 - c)); //异或操作 相同取0 相反取1(这个取值是二进制层面的)
        }
        return ans;
    }

    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/construct-k-palindrome-strings/ 1400. 构造 K 个回文字符串
     * 主要思路是 偶数的字符肯定可以构成回文字每一个回文字最多可以携带一个额外的字符放在字符串中间 所以可以消掉一个奇数的字符
     * create time: 2020-6-5 10:42
     * <p>
     * return a
     *
     * @params
     */
    public boolean canConstruct(String s, int k) {
        int[] dp = new int[26];
        if (k == s.length()) return true;
        if (k > s.length()) return false;
        for (int i = 0; i < s.length(); i++) {
            dp[s.charAt(i) - 97]++;
        }
        int num2 = 0;
        int num1 = 0;
        for (int i = 0; i < dp.length; i++) {
            if (dp[i] % 2 == 0) num2++;
            else num1++;
        }
        if (num1 > k) return false;
        return true;

    }

    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/partition-labels/ 763. 划分字母区间
     * 双指针贪心
     * left指针初始化指向0 right指向len-1
     * right一直--直到找到和left相同的 然后left++(但是要比right要小) right要重置到len-1;
     * create time: 2020-6-5 10:56
     *
     * @return java.util.List<java.lang.Integer>
     * @params [S]
     */
    public static List<Integer> partitionLabels(String S) {
        int[] last = new int[26];
        for (int i = 0; i < S.length(); ++i)
            last[S.charAt(i) - 'a'] = i;//找到每一个字母最后出现的位置

        int j = 0, anchor = 0;
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < S.length(); ++i) {
            j = Math.max(j, last[S.charAt(i) - 'a']);
            if (i == j) {
                ans.add(i - anchor + 1);
                anchor = i + 1;
            }
        }
        return ans;
    }

    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/bag-of-tokens/  948. 令牌放置
     * create time: 2020-6-5 14:51
     *
     * @return int
     * @params [tokens, P]
     */
    public int bagOfTokensScore(int[] tokens, int P) {
        int res = 0;
        int left = 0;
        int right = tokens.length - 1;
        Arrays.sort(tokens);
        while (left < right) {
            if (P - tokens[left] < 0) {
                if (res > 0) {
                    res--;
                    P += tokens[right--];
                } else {
                    return 0;
                }
            }
            res++;
            P -= tokens[left++];
        }
        if (left == right && P - tokens[left] >= 0) {
            res++;
        }
        return res;
    }

    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/edit-distance/
     * create time: 2020-6-6 22:18
     *
     * @return int
     * @params [word1, word2]
     */
    public int minDistance(String word1, String word2) {
        int n1 = word1.length();
        int n2 = word2.length();
        int[][] dp = new int[n1 + 1][n2 + 1];
        // dp[0][0...n2]的初始值
        for (int j = 1; j <= n2; j++)
            dp[0][j] = dp[0][j - 1] + 1;
        // dp[0...n1][0] 的初始值
        for (int i = 1; i <= n1; i++) dp[i][0] = dp[i - 1][0] + 1;
        // 通过公式推出 dp[n1][n2]
        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                // 如果 word1[i] 与 word2[j] 相等。第 i 个字符对应下标是 i-1
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;
                }
            }
        }
        return dp[n1][n2];
    }
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/largest-1-bordered-square/submissions/
     * create time: 2020-6-7 22:52
     * @params [grid]
     * @return int
     */
    //    使用3维数组dp[n + 1][m + 1][2](数组下标从1开始)
//    dp[i][j][0]:表示第i行第j列的1往 左边 最长连续的1的个数
//    dp[i][j][1]:表示第i行第j列的1往 上面 最长连续的1的个数
    public int largest1BorderedSquare(int[][] grid) {

        int n = grid.length, m = 0, res = 0;
        if (n == 0) return 0;
        m = grid[0].length;
        int[][][] dp = new int[n + 1][m + 1][2];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                int d = 0;
                if (grid[i - 1][j - 1] == 1) {    //因为dp数组下标从1开始
                    //更新dp[i][j]的2个状态
                    dp[i][j][0] = dp[i][j - 1][0] + 1;
                    dp[i][j][1] = dp[i - 1][j][1] + 1;
                    //以当前的1为右下角要构成正方形,其边长最长只可能是左边最长连续的1与上面最长连续的1的个数取最小值
                    d = Math.min(dp[i][j - 1][0], dp[i - 1][j][1]); //d表示不包括当前1的最长长度
                    while (d > 0) {
                        //判断第i行的第j-d列的上面1的个数,和第i-d行的第j列的左边的1的个数是否都大于d(大于d,不能等,因为d比实际边长小1)
                        if (dp[i][j - d][1] > d && dp[i - d][j][0] > d) break; //判断边长为d能否构成正方形,若能break
                        d--;    //若不能就取次小的边长
                    }
                    res = Math.max(res, d + 1);
                }
            }
        }
        return res * res;
    }
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/delete-and-earn/
     * create time: 2020-6-7 22:52
     * @params [nums]
     * @return int
     */
    public int deleteAndEarn(int[] nums) {
        
        if (nums == null || nums.length == 0) {
            return 0;
        } else if (nums.length == 1) {
            return nums[0];
        }
        int len = nums.length;
        int max = nums[0];
        for (int i = 1; i < len; ++i) {
            max = Math.max(max, nums[i]);
        }
//      构造一个新的数组all
        int[] all = new int[max + 1];
        for (int item : nums) {
            all[item]++;
        }
        int[] dp = new int[max + 1];
        dp[1] = all[1] * 1;
        dp[2] = Math.max(dp[1], all[2] * 2);
//      动态规划求解
        for (int i = 2; i <= max; ++i) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + (i * all[i]));
        }
        return dp[max];
    }

    public static void main(String[] args) throws IOException {
        partitionLabels("eaaaabaaec");
        int[][] a = {{1, 1, 1}};
    }
}
